use async_trait::async_trait;
use rustcloud_core::{
    LoadBalancer, ServiceInstance, ServiceResult, RequestContext, InstanceMetrics, StrategyInfo
};
use std::sync::atomic::{AtomicUsize, Ordering};
use std::collections::{HashMap, BTreeMap};
use std::sync::{Arc, RwLock, Mutex};
use std::hash::{Hash, Hasher};
use std::collections::hash_map::DefaultHasher;
use std::time::{Duration, SystemTime};
use sha2::{Sha256, Digest};

/// 平滑加权轮询算法
/// 
/// 该算法避免了传统加权轮询可能导致的"突发"效应，
/// 能够更均匀地分布请求到各个实例
pub struct SmoothWeightedRoundRobin {
    /// 实例权重状态
    instance_weights: Arc<Mutex<HashMap<String, InstanceWeight>>>,
}

/// 实例权重状态
#[derive(Debug, Clone)]
struct InstanceWeight {
    /// 配置权重（固定不变）
    weight: f64,
    /// 当前权重（动态变化）
    current_weight: f64,
    /// 生效权重（用于计算）
    effective_weight: f64,
}

impl InstanceWeight {
    fn new(weight: f64) -> Self {
        Self {
            weight,
            current_weight: 0.0,
            effective_weight: weight,
        }
    }
}

impl SmoothWeightedRoundRobin {
    pub fn new() -> Self {
        Self {
            instance_weights: Arc::new(Mutex::new(HashMap::new())),
        }
    }
    
    /// 更新实例权重
    fn update_instance_weights(&self, instances: &[ServiceInstance]) {
        if let Ok(mut weights) = self.instance_weights.lock() {
            // 移除不再存在的实例
            let current_instances: Vec<String> = instances
                .iter()
                .map(|i| i.address())
                .collect();
            weights.retain(|address, _| current_instances.contains(address));
            
            // 添加或更新现有实例
            for instance in instances {
                let address = instance.address();
                weights.entry(address).or_insert_with(|| InstanceWeight::new(instance.weight));
                
                // 更新权重如果发生变化
                if let Some(weight_info) = weights.get_mut(&instance.address()) {
                    if weight_info.weight != instance.weight {
                        weight_info.weight = instance.weight;
                        weight_info.effective_weight = instance.weight;
                    }
                }
            }
        }
    }
    
    /// 平滑加权轮询选择算法
    fn smooth_weighted_select(&self, instances: &[ServiceInstance]) -> Option<ServiceInstance> {
        if instances.is_empty() {
            return None;
        }
        
        let mut weights = self.instance_weights.lock().ok()?;
        
        let mut total_weight = 0.0;
        let mut selected_instance: Option<ServiceInstance> = None;
        let mut best_current_weight = f64::NEG_INFINITY;
        
        // 更新所有实例的当前权重，选择当前权重最高的实例
        for instance in instances {
            let address = instance.address();
            if let Some(weight_info) = weights.get_mut(&address) {
                // 增加当前权重
                weight_info.current_weight += weight_info.effective_weight;
                total_weight += weight_info.effective_weight;
                
                // 选择当前权重最高的实例
                if weight_info.current_weight > best_current_weight {
                    best_current_weight = weight_info.current_weight;
                    selected_instance = Some(instance.clone());
                }
            }
        }
        
        // 减少被选中实例的当前权重
        if let Some(ref selected) = selected_instance {
            if let Some(weight_info) = weights.get_mut(&selected.address()) {
                weight_info.current_weight -= total_weight;
            }
        }
        
        selected_instance
    }
}

#[async_trait]
impl LoadBalancer for SmoothWeightedRoundRobin {
    async fn select(
        &self,
        _service_name: &str,
        instances: &[ServiceInstance],
    ) -> ServiceResult<Option<ServiceInstance>> {
        if instances.is_empty() {
            return Ok(None);
        }
        
        // 过滤健康的实例
        let healthy_instances: Vec<ServiceInstance> = instances
            .iter()
            .filter(|instance| instance.healthy && instance.weight > 0.0)
            .cloned()
            .collect();
        
        if healthy_instances.is_empty() {
            return Ok(None);
        }
        
        // 更新实例权重
        self.update_instance_weights(&healthy_instances);
        
        // 执行平滑加权选择
        Ok(self.smooth_weighted_select(&healthy_instances))
    }

    fn name(&self) -> &str {
        "smooth_weighted_round_robin"
    }
    
    fn get_strategy_info(&self) -> StrategyInfo {
        StrategyInfo {
            name: "Smooth Weighted Round Robin".to_string(),
            description: "平滑加权轮询算法，避免突发流量，更均匀地分布请求".to_string(),
            requires_session_affinity: false,
            supports_weighted_routing: true,
        }
    }
    
    async fn update_instance_metrics(&self, instance: &ServiceInstance, metrics: InstanceMetrics) {
        // 根据实例性能动态调整有效权重
        if let Ok(mut weights) = self.instance_weights.lock() {
            if let Some(weight_info) = weights.get_mut(&instance.address()) {
                // 根据响应时间和成功率调整有效权重
                let response_time_factor = if metrics.response_time > Duration::from_millis(1000) {
                    0.5 // 响应时间过长，降低权重
                } else if metrics.response_time < Duration::from_millis(100) {
                    1.2 // 响应时间很短，提高权重
                } else {
                    1.0
                };
                
                let success_rate_factor = if metrics.success_rate < 0.9 {
                    0.3 // 成功率低，大幅降低权重
                } else if metrics.success_rate > 0.99 {
                    1.1 // 成功率很高，略微提高权重
                } else {
                    1.0
                };
                
                weight_info.effective_weight = weight_info.weight * response_time_factor * success_rate_factor;
                
                // 确保有效权重不小于0
                weight_info.effective_weight = weight_info.effective_weight.max(0.0);
            }
        }
    }
}

/// 改进的一致性哈希算法
/// 
/// 支持虚拟节点权重分配、多种哈希算法、节点故障检测
pub struct AdvancedConsistentHash {
    /// 虚拟节点数量
    virtual_nodes: usize,
    /// 哈希算法类型
    hash_algorithm: HashAlgorithm,
    /// 实例性能指标
    instance_metrics: Arc<RwLock<HashMap<String, InstanceMetrics>>>,
}

#[derive(Debug, Clone)]
pub enum HashAlgorithm {
    DefaultHash,
    Sha256,
    Fnv,
}

impl AdvancedConsistentHash {
    pub fn new() -> Self {
        Self {
            virtual_nodes: 160,
            hash_algorithm: HashAlgorithm::Sha256,
            instance_metrics: Arc::new(RwLock::new(HashMap::new())),
        }
    }
    
    pub fn with_virtual_nodes(virtual_nodes: usize) -> Self {
        Self {
            virtual_nodes,
            hash_algorithm: HashAlgorithm::Sha256,
            instance_metrics: Arc::new(RwLock::new(HashMap::new())),
        }
    }
    
    pub fn with_hash_algorithm(mut self, algorithm: HashAlgorithm) -> Self {
        self.hash_algorithm = algorithm;
        self
    }
    
    /// 计算字符串的哈希值
    fn hash(&self, key: &str) -> u64 {
        match self.hash_algorithm {
            HashAlgorithm::DefaultHash => {
                let mut hasher = DefaultHasher::new();
                key.hash(&mut hasher);
                hasher.finish()
            }
            HashAlgorithm::Sha256 => {
                let mut hasher = Sha256::new();
                hasher.update(key.as_bytes());
                let result = hasher.finalize();
                // 取前8字节作为u64
                u64::from_be_bytes([
                    result[0], result[1], result[2], result[3],
                    result[4], result[5], result[6], result[7],
                ])
            }
            HashAlgorithm::Fnv => {
                // FNV-1a哈希算法的简单实现
                let mut hash = 0xcbf29ce484222325u64;
                for byte in key.bytes() {
                    hash ^= byte as u64;
                    hash = hash.wrapping_mul(0x100000001b3);
                }
                hash
            }
        }
    }
    
    /// 构建带权重的一致性哈希环
    fn build_weighted_hash_ring(&self, instances: &[&ServiceInstance]) -> BTreeMap<u64, ServiceInstance> {
        let mut ring = BTreeMap::new();
        
        for instance in instances {
            // 根据实例权重决定虚拟节点数量
            let node_count = (self.virtual_nodes as f64 * instance.weight / 100.0).max(1.0) as usize;
            
            for i in 0..node_count {
                let virtual_key = format!("{}:{}:{}", instance.address(), instance.weight, i);
                let hash_value = self.hash(&virtual_key);
                ring.insert(hash_value, (*instance).clone());
            }
        }
        
        ring
    }
    
    /// 根据键找到对应的实例（考虑性能指标）
    fn find_best_instance(&self, key: &str, ring: &BTreeMap<u64, ServiceInstance>) -> Option<ServiceInstance> {
        if ring.is_empty() {
            return None;
        }
        
        let hash = self.hash(key);
        
        // 找到哈希环上的候选节点（前3个）
        let mut candidates = Vec::new();
        
        // 从哈希值开始向后找
        for (_, instance) in ring.range(hash..) {
            if candidates.len() < 3 && !candidates.iter().any(|i: &ServiceInstance| i.address() == instance.address()) {
                candidates.push(instance.clone());
            }
            if candidates.len() >= 3 {
                break;
            }
        }
        
        // 如果不够3个，从环的开头补充
        if candidates.len() < 3 {
            for (_, instance) in ring.iter() {
                if candidates.len() < 3 && !candidates.iter().any(|i: &ServiceInstance| i.address() == instance.address()) {
                    candidates.push(instance.clone());
                }
                if candidates.len() >= 3 {
                    break;
                }
            }
        }
        
        if candidates.is_empty() {
            return None;
        }
        
        // 根据性能指标选择最佳实例
        let metrics = self.instance_metrics.read().ok()?;
        
        let mut best_instance = candidates[0].clone();
        let mut best_score = self.calculate_instance_score(&best_instance, &metrics);
        
        for candidate in candidates.iter().skip(1) {
            let score = self.calculate_instance_score(candidate, &metrics);
            if score > best_score {
                best_score = score;
                best_instance = candidate.clone();
            }
        }
        
        Some(best_instance)
    }
    
    /// 计算实例得分（综合考虑响应时间、成功率、连接数等）
    fn calculate_instance_score(&self, instance: &ServiceInstance, metrics: &HashMap<String, InstanceMetrics>) -> f64 {
        if let Some(metric) = metrics.get(&instance.address()) {
            let response_time_score = if metric.response_time > Duration::from_millis(1000) {
                0.1
            } else if metric.response_time < Duration::from_millis(100) {
                1.0
            } else {
                1.0 - (metric.response_time.as_millis() as f64 / 1000.0).min(1.0)
            };
            
            let success_rate_score = metric.success_rate;
            
            let connection_score = if metric.active_connections > 1000 {
                0.1
            } else {
                1.0 - (metric.active_connections as f64 / 1000.0).min(0.9)
            };
            
            // 加权计算总分
            response_time_score * 0.4 + success_rate_score * 0.4 + connection_score * 0.2
        } else {
            // 没有指标数据，返回基础分数
            0.5
        }
    }
}

#[async_trait]
impl LoadBalancer for AdvancedConsistentHash {
    async fn select(
        &self,
        service_name: &str,
        instances: &[ServiceInstance],
    ) -> ServiceResult<Option<ServiceInstance>> {
        if instances.is_empty() {
            return Ok(None);
        }
        
        // 过滤健康的实例
        let healthy_instances: Vec<&ServiceInstance> = instances
            .iter()
            .filter(|instance| instance.healthy)
            .collect();
        
        if healthy_instances.is_empty() {
            return Ok(None);
        }
        
        // 构建加权哈希环
        let ring = self.build_weighted_hash_ring(&healthy_instances);
        
        // 使用服务名作为哈希键
        let instance = self.find_best_instance(service_name, &ring);
        
        Ok(instance)
    }

    async fn select_with_context(
        &self,
        service_name: &str,
        instances: &[ServiceInstance],
        context: &RequestContext,
    ) -> ServiceResult<Option<ServiceInstance>> {
        if instances.is_empty() {
            return Ok(None);
        }
        
        // 过滤健康的实例
        let healthy_instances: Vec<&ServiceInstance> = instances
            .iter()
            .filter(|instance| instance.healthy)
            .collect();
        
        if healthy_instances.is_empty() {
            return Ok(None);
        }
        
        // 构建加权哈希环
        let ring = self.build_weighted_hash_ring(&healthy_instances);
        
        // 构建复合哈希键，支持会话亲和性
        let hash_key = if let Some(session_id) = &context.session_id {
            format!("{}:session:{}", service_name, session_id)
        } else if let Some(user_id) = &context.user_id {
            format!("{}:user:{}", service_name, user_id)
        } else if let Some(trace_id) = &context.trace_id {
            format!("{}:trace:{}", service_name, trace_id)
        } else {
            service_name.to_string()
        };
        
        let instance = self.find_best_instance(&hash_key, &ring);
        
        Ok(instance)
    }

    fn name(&self) -> &str {
        "advanced_consistent_hash"
    }
    
    fn get_strategy_info(&self) -> StrategyInfo {
        StrategyInfo {
            name: "Advanced Consistent Hash".to_string(),
            description: "改进的一致性哈希算法，支持权重分配和性能指标".to_string(),
            requires_session_affinity: true,
            supports_weighted_routing: true,
        }
    }
    
    async fn update_instance_metrics(&self, instance: &ServiceInstance, metrics: InstanceMetrics) {
        if let Ok(mut metric_map) = self.instance_metrics.write() {
            metric_map.insert(instance.address(), metrics);
            
            // 清理过期数据（超过5分钟的数据）
            let now = SystemTime::now();
            metric_map.retain(|_, metric| {
                now.duration_since(metric.last_updated).unwrap_or(Duration::from_secs(0)) < Duration::from_secs(300)
            });
        }
    }
}

/// 最少连接数负载均衡算法
pub struct LeastConnections {
    /// 实例连接数统计
    connection_counts: Arc<RwLock<HashMap<String, u32>>>,
}

impl LeastConnections {
    pub fn new() -> Self {
        Self {
            connection_counts: Arc::new(RwLock::new(HashMap::new())),
        }
    }
    
    /// 增加实例连接数
    pub async fn increment_connections(&self, instance: &ServiceInstance) {
        if let Ok(mut counts) = self.connection_counts.write() {
            *counts.entry(instance.address()).or_insert(0) += 1;
        }
    }
    
    /// 减少实例连接数
    pub async fn decrement_connections(&self, instance: &ServiceInstance) {
        if let Ok(mut counts) = self.connection_counts.write() {
            if let Some(count) = counts.get_mut(&instance.address()) {
                *count = count.saturating_sub(1);
            }
        }
    }
}

#[async_trait]
impl LoadBalancer for LeastConnections {
    async fn select(
        &self,
        _service_name: &str,
        instances: &[ServiceInstance],
    ) -> ServiceResult<Option<ServiceInstance>> {
        if instances.is_empty() {
            return Ok(None);
        }
        
        // 过滤健康的实例
        let healthy_instances: Vec<&ServiceInstance> = instances
            .iter()
            .filter(|instance| instance.healthy)
            .collect();
        
        if healthy_instances.is_empty() {
            return Ok(None);
        }
        
        // 找到连接数最少的实例
        let counts = self.connection_counts.read().map_err(|_| 
            rustcloud_core::ServiceError::LoadBalancerError("Failed to read connection counts".to_string())
        )?;
        
        let mut best_instance = healthy_instances[0];
        let mut min_connections = counts.get(&best_instance.address()).unwrap_or(&0);
        
        for &instance in healthy_instances.iter().skip(1) {
            let connections = counts.get(&instance.address()).unwrap_or(&0);
            if connections < min_connections {
                min_connections = connections;
                best_instance = instance;
            }
        }
        
        Ok(Some(best_instance.clone()))
    }

    fn name(&self) -> &str {
        "least_connections"
    }
    
    fn get_strategy_info(&self) -> StrategyInfo {
        StrategyInfo {
            name: "Least Connections".to_string(),
            description: "最少连接数算法，选择当前连接数最少的实例".to_string(),
            requires_session_affinity: false,
            supports_weighted_routing: false,
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use rustcloud_core::ServiceInstance;
    use std::time::Duration;
    
    #[tokio::test]
    async fn test_smooth_weighted_round_robin() {
        let lb = SmoothWeightedRoundRobin::new();
        
        let instances = vec![
            ServiceInstance::new("service1", "127.0.0.1", 8081, "http").with_weight(5.0).unwrap(),
            ServiceInstance::new("service1", "127.0.0.1", 8082, "http").with_weight(3.0).unwrap(),
            ServiceInstance::new("service1", "127.0.0.1", 8083, "http").with_weight(1.0).unwrap(),
        ];
        
        // 测试多次选择，验证权重分布
        let mut selections = HashMap::new();
        for _ in 0..90 {
            if let Ok(Some(instance)) = lb.select("service1", &instances).await {
                *selections.entry(instance.port).or_insert(0) += 1;
            }
        }
        
        println!("Selections: {:?}", selections);
        
        // 验证权重比例大致正确（5:3:1）
        let port_8081_count = selections.get(&8081).unwrap_or(&0);
        let port_8082_count = selections.get(&8082).unwrap_or(&0);
        let port_8083_count = selections.get(&8083).unwrap_or(&0);
        
        assert!(*port_8081_count > *port_8082_count);
        assert!(*port_8082_count > *port_8083_count);
    }
    
    #[tokio::test]
    async fn test_advanced_consistent_hash() {
        let lb = AdvancedConsistentHash::new();
        
        let instances = vec![
            ServiceInstance::new("service1", "127.0.0.1", 8081, "http"),
            ServiceInstance::new("service1", "127.0.0.1", 8082, "http"),
            ServiceInstance::new("service1", "127.0.0.1", 8083, "http"),
        ];
        
        // 相同的服务名应该总是选择相同的实例
        let first_selection = lb.select("test-service", &instances).await.unwrap().unwrap();
        let second_selection = lb.select("test-service", &instances).await.unwrap().unwrap();
        
        assert_eq!(first_selection.address(), second_selection.address());
        
        // 不同的服务名可能选择不同的实例
        let different_selection = lb.select("different-service", &instances).await.unwrap().unwrap();
        
        // 至少要有一个实例被选中
        assert!([&first_selection, &different_selection].iter().any(|i| instances.contains(i)));
    }
}